package com.yc.thread.pro3_bestMatching;

/**
 * @author zwei
 * @create 2024-07-24 19:45
 * 最短编辑算法
 */
public class EditDistance {
    public static int calculate(String word1,String word2){
        //初始化一个矩阵，以保存两个单词的距离
        int[][]distance=new int[word1.length()+1][word2.length()+1];
        //初始化第一行
        for (int i = 0; i < word1.length()+1; i++)
            distance[i][0]=i;
        //初始化第一列
        for (int j = 0; j < word2.length()+1; j++)
            distance[0][j]=j;
        //计算距离
        for (int i=1;i<word1.length()+1;i++){
            for (int j=1;j<word2.length()+1;j++){
                //如果字符串的第i个字符和第j个字符不相等，将编辑距离设为左上角位置的+1；否则保持不变
                if (word1.charAt(i-1)==word2.charAt(j-1)){
                    //相等  将左上角的值做为[i][j]
                    distance[i][j]=distance[i-1][j-1];
                }else {
                    //不相等  将左上角的值+1做为[i][j]
                    distance[i][j]=min(distance[i-1][j-1]+1,distance[i-1][j]+1,distance[i][j-1]+1);
                }
            }
        }
        return distance[word1.length()][word2.length()];
    }
    private static int min(int a,int b,int c){
        return Math.min(a,Math.min(b,c));
    }
}
